package 算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

public class LCP07传递信息 {
    public static void main(String[] args) {
        Long l = System.currentTimeMillis();
        for (int i = 0; i < 8888;i++){
            new LCP07传递信息().messageD(new int[]{1,7,1,1,2,8,9,7,6,7,1,7,1,1,2,8,9,7,6,7});
        }
        System.out.println(System.currentTimeMillis()-l);
    }
    static int coun = 0;
    //返回最优预约时间__动态规划
    public int messageD(int[] nums){
        if (nums.length<1){
            return 0;
        }
        int[][] md = new int[nums.length][2];
        md[0][0] = 0;
        md[0][1] = nums[0];
        for (int i = 1;i < nums.length; i++){
            md[i][0] = Math.max(md[i-1][0],md[i-1][1]);
            md[i][1] = md[i-1][0]+nums[i];
        }
        return Math.max(md[nums.length-1][0],md[nums.length-1][1]);
    }
    //返回最优预约时间__递归
    static Map<int[],Integer> map = new HashMap<>();
    public int massage(int[] nums) {
        coun++;
        if(map.get(nums) != null){
            return map.get(nums);
        }
        if(nums.length == 0) return 0;
        if(nums.length == 1){
            return nums[0];
        }
        int v1[] = splie(nums.clone(),1);
        int k1 = nums[0]+massage(v1);
        int v2[] =splie(nums.clone(),2);
        int k2 = nums[1]+massage(v2);


        int k3 = Math.max(k1,k2);
        map.put(nums,k3);
        return k3;
    }
    //返回第n折数组,不要第n个，从0开始
    public int[] splie(int[] nums,int n){
        if(nums.length-n-1 <= 0){
            return new int[0];
        }
        int[] res = new int[nums.length-n-1];
        int j = n;
        while (n < nums.length-1){
            res[n-j] = nums[n+1];
            n++;
        }
        return res;
    }
    public static int uniquePaths(int m, int n) {

        int[][] dt = new int[m+1][n+1]; //0格不用了

        //初始化数据
        dt[1][1] = 1;
        for(int i = 0; i < dt.length; i++){
            dt[i][0] = 0;

        }
        for (int i = 0; i < dt[0].length; i++){
            dt[0][i] = 0;
        }
        for (int i = 1; i < dt.length; i++){
            for (int j = 1; j < dt[0].length; j++){
                if(i != 1 || j != 1)
                    dt[i][j] = dt[i-1][j]+dt[i][j-1];
            }
        }
        return dt[m-1][n]+dt[m][n-1];
    }
    public static int maxProduct(int[] nums) {
        int res = 0;
        int temp;
        for(int i = 0; i < nums.length; i++){
            res = res > nums[i] ? res:nums[i];
            temp = nums[i];

            for(int j = i+1; j < nums.length; j++){
                temp *= nums[j];
                res = res > temp ? res:temp;
            }
        }
        return res;
    }
    static int ij =0;
    static Map<Integer, List<Integer>> ra = new HashMap();
    //如果k为1，检测relation[][n]的值是否为一，否则向下传递,从下往上找
    public static int numWays(int n, int[][] relation, int k) {
        if(ra.size() == 0){
            for (int[] ints : relation) {
                if(ra.get(ints[1]) == null){
                    ra.put(ints[1],new ArrayList<Integer>());
                }
                ra.get(ints[1]).add(ints[0]);
            }
        }
        AtomicInteger i = new AtomicInteger(0);
        if(k==1){
            List<Integer> list = ra.get(n-1) == null ? new ArrayList<>():ra.get(n-1);

            list.forEach(e->{
                if(e==0){
                    i.set(1);
                }
            });
            return i.get();
        }
        //{4,5}->{2,4}->{0,2},{3,5}
//        for (int[] ints : relation) {
            List<Integer> list = ra.get(n-1) == null ? new ArrayList<>():ra.get(n-1);
            list.forEach(e->{
                i.addAndGet(numWays(e+1, relation, k - 1));
//                if(e==0){
//                    i.addAndGet(1);
//                }
            });

//        }
        return i.get();
    }

}
